Processing math: 100%
【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973 | Qiuly's blog!

【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973

Posted on | Edited on | In | Comments:

这道题一共有两问，第一问瞎搞 DP ，第二问如果直接 DP 的话复杂度是 O(n4) 的过不去，这个时候需要用到决策单调性优化复杂度就可以降低至 O(n3) ，这样就过了。我们先来讨论一下第一问的做法。

时间的范围太大了，我们需要离散化一下。离散化后时间就控制在 0 到 2n 的范围内了。

首先可以发现最终的答案一定就是一段一段时间，每一段时间内的活动都是在同一个会场举行。我们可以预处理一个 totl,r 表示完全在时间 l,r 之内的活动有多少个。计算直接暴力，预处理的复杂度为 O(n3) 。

然后设一个 prei,j​ 表示 1​ 到 i​ 的时间一个会场的活动数为 j​ 时另一个会场的最大活动数。那么转移的话我们枚举一个时间 k​ ，然后考虑 k​ 到 i​ 这段时间中的所有活动分配给哪个会场即可。可以得到转移方程：

prei,j=imaxk=1{prek,j+totk,i,prek,j−totk,i}​

这里我们 pre 方程的定义中”一个会场”就是一号会场，”另一个会场”就是二号会场。prek,j+totk,i 就是将 k 到 i 这段时间中所有活动都分配给了二号会场，prek,j−totk,i 很显然就是分配给了一号会场。计算时枚举 i,j,k ，复杂度是 O(n3) 。(其实准确的复杂度带个常数，因为 i 枚举的是时间，而时间最大是 2n 的) 。

我们设离散化后时间总长为 m ，那么答案显然为 mmaxi=1{min(prem,i,i)} 。接下来我们解决第二问。

我们的 totl,r 统计的就是完全在时间 l,r 的区间有多少个。那么对于第 i 个活动，设该活动的起始时间与终止时间分别为 si,ti ，那么我们再考虑一对 x,y  (x≤si,ti≤y) ，那么如果我们将答案计算上 totx,y ，那么也就选择了第 i 个活动了。

我们设 fi,j 表示一号会场强制选择 i 到 j 时间中的所有活动时的最优答案。(注意这里的最优答案就是两个会场中活动少的一方的最大值，我们只是考虑在一号会场强制选择 i 到 j​ 中的所有活动的情况下考虑最优的全局答案) 。

继续看向一号会场，假设在 i 前面的时间中一号会场已经合法举办了 x 场活动，在 j 后面的时间中也合法举办了 y 场活动。那么我们枚举 i,j,x,y 也可以得到二号会场的活动数：i 前面的时间种有 prei,x 场活动，j 后面的时间中有……诶这里用 pre 貌似不是很好表示诶，于是我们新定义一个 suf ，sufi,j 表示 i 到 m 的时间一个会场的活动数为 j 时另一个会场的最大活动数，suf 的状态转移方程和 pre 的同理。

枚举 i,j,x,y 后就可以得到两个会场的活动个数，那么就可以直接算答案了：

fi,j=mmaxx=1mmaxy=1{min(x+toti,j+y,prei,x+sufj,y)}​

但是这样子的复杂度是 O(n4)​ 的，过不了。

不过，我们会发现，对于单调递增的 x ，对应的最优的 y 一定是单调递减的 。为什么呢？首先对于一个单调递增的 i ，pre?i,suf?i 一定是单调递减的( ? 为任意数) 。那么如果对于单调递增的 x ，prei,x 一定是单调递减的，这个时候如果 y 单调递增也就意味着 sufj,y 会单调递减，那么 x+toti,j+y 和 prei,x+sufj,y 将会越拉越大，对于答案显然是不利的。反过来，如果 y 是单调递减的，那么就会相对比较均衡。(感性理解理解……)

那么我们就不需要枚举 y 了，只需要扫一扫就好了，最终计算 f 的时间复杂度为 O(n3) 。

最终统计答案的时候，对于一个活动 i ，我们的答案显然为 simaxx=1mmaxy=tifx,y 。必须满足 x≤si,ti≤y ，因为这样就会满足一定会选择第 i 个活动。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define F(i,j,k) for((i)=(j);(i)<=(k);++i)
#define R(i,j,k) for((i)=(j);(i)>=(k);--i)

const int N=4e2+9;
const int inf=1e9+9;

int n,m,i,j,k,l,r,s[N],t[N],b[N];
int tot[N][N],pre[N][N],suf[N][N],f[N][N];

inline int IN() {
    char ch;bool flag=0;int x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;return x;
}

inline int calc(int x,int y) 
{return min(x+tot[l][r]+y,pre[l][x]+suf[r][y]);}   

int main() {
    n=IN();
    F(i,1,n) b[++m]=s[i]=IN(),b[++m]=t[i]=IN()+s[i];
    sort(b+1,b+1+m),
    m=unique(b+1,b+1+m)-b-1;/*离散化去重*/
    F(i,1,n) {
        s[i]=lower_bound(b+1,b+1+m,s[i])-b;
        t[i]=lower_bound(b+1,b+1+m,t[i])-b;
        F(l,1,s[i]) R(r,m,t[i]) ++tot[l][r];/*计算出tot*/
    }
    F(i,1,m) F(j,1,n) pre[i][j]=suf[i][j]=-inf;/*初始化*/ 
    /*----------计算出pre和suf----------*/
    F(i,1,m) F(j,0,tot[1][i]) F(k,1,i) {
        pre[i][j]=max(pre[i][j],pre[k][j]+tot[k][i]);
        if(j>=tot[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-tot[k][i]]);
    }
    R(i,m,1) F(j,0,tot[i][m]) F(k,i,m) {
        suf[i][j]=max(suf[i][j],suf[k][j]+tot[i][k]);
        if(j>=tot[i][k]) suf[i][j]=max(suf[i][j],suf[k][j-tot[i][k]]);
    }
    /*计算f*/
    F(l,1,m) F(r,l+1,m) for(int y=n,x=0;x<=n;++x) {/*y当做指针扫一遍*/
        int old_calc=calc(x,y),new_calc;
        while(y&&old_calc<=(new_calc=calc(x,y-1))) --y,old_calc=new_calc;
        f[l][r]=max(f[l][r],calc(x,y));/*转移*/
    }
    /*输出答案*/
    int ans=0;
    F(i,1,n) ans=max(ans,min(pre[m][i],i));
    printf("%d\n",ans);/*第一问*/
    F(i,1,n) {
        ans=0;
        F(l,1,s[i]) R(r,m,t[i]) ans=max(ans,f[l][r]);
        printf("%d\n",ans);/*第二问*/
    }return 0;
}

本文标题:【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973

文章作者:Qiuly

发布时间:2019年04月22日 - 00:00

最后更新:2019年04月23日 - 08:42

原始链接:http://qiulyblog.github.io/2019/04/22/[题解]luoguP1973/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Powered By Valine
v1.5.2